package hot.huisu;

import java.util.LinkedList;
import java.util.Queue;

public class A994 {
}

class Solution1 {
    //方向数组
    int[] d1=new int[]{0,1,-1,0};
    int[] d2=new int[]{1,0,0,-1};
    public int orangesRotting(int[][] grid) {

        int sum=0;
        int n=grid.length;
        int m=grid[0].length;
        Queue<int[]> queue=new LinkedList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1)sum++; //统计新鲜橘子数量
                if(grid[i][j]==2)queue.offer(new int[]{i,j});//将腐烂橘子加入数组
            }
        }
        int time=0;
        int size;//当前队列腐烂橘子数量
        while(!queue.isEmpty()){
            size= queue.size();
            for(int i=0;i<size;i++){
                int[] poll = queue.poll();
                int a=poll[0];
                int b=poll[1];
                for(int j=0;j<4;j++){
                    int x=a+d1[j];
                    int y=b+d2[j];
                    if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1) {
                        queue.offer(new int[]{x,y});
                        grid[x][y]=2;
                        sum--;
                    }
                }
            }
            //如果有被腐烂的，才增加时间
            if(!queue.isEmpty())time++;
        }
        return sum==0?time:-1;
    }
}